01｜二分答案（Binary Search on Answer）（知识笔记）

对应课程：lessons/01-complexity-and-binary-search/02-binary-search-on-answer.md

识别信号（很像“最优化”，但能决策化）

• “最小的最大值 / 最大化最小值”
• “是否能在 k 次操作内做到”
• “给定阈值 X，能否达成目标”

解题流程（建议固定写在草稿纸上）

1. 写出决策问题：check(X)
2. 写出单调方向：
   • X 变大更容易？还是更难？
3. 找上下界：
   • lo：一定不行或理论最小
   • hi：一定可行（宁可取大一点）
4. 用二分找到分界

check 的三种高频形态

形态 A：计数/资源

给定 X，计算“需要多少资源/操作次数”，判断是否 <= k。

形态 B：贪心构造

给定 X，用贪心尝试构造可行解（能构造则 true）。

形态 C：DP/图（少见但存在）

给定 X，判断是否存在路径/方案满足限制。

常见坑

• 上界取小：导致“答案不在区间里”
• check 溢出：总和/次数可能到 1e18
• 单调性证明不足：被一个反例击穿

自检

• [ ] 用最小样例手算 check
• [ ] 上界是否“必然可行”？
• [ ] check 是否严格遵守题意（别偷换概念）

个人坑位

• （例）我经常在 check 里写贪心，但贪心没有证明导致错